﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Xml;
using System.IO;

using HeapModel.ProgInfo;
using HeapModel.ConcreteMemory;

using System.Diagnostics.Contracts;
using System.Diagnostics;

namespace HeapModel.RegionPartition
{
	/// <summary>
	/// This class defines the set of operations for manipulating the nodes in the basic heap graph.
	/// </summary>
	[DebuggerDisplay("Count = {NodeCount}")]
	public sealed class RegionGraph
	{
		public readonly ConcreteHeap CMem;

		private readonly HashSet<RegionNode> m_nodes;
		private readonly Dictionary<ConcreteNode, RegionNode> m_conctorgnmap;

		private readonly Dictionary<RegionNode, HashSet<RegionNode>> m_finalrelmap;

		public readonly Dictionary<RegionNode, List<RegionEdgeInfo>> FinalSuccMap;
		public readonly Dictionary<RegionNode, List<RegionEdgeInfo>> FinalPredMap;

		private readonly RecursiveTypeInfo m_typeInfo;

		[ContractInvariantMethod]
		private void HeapGraphInvariant()
		{
			Contract.Invariant(this.CMem != null);
			Contract.Invariant(this.m_nodes != null);
			Contract.Invariant(this.m_conctorgnmap != null);
			Contract.Invariant(this.m_typeInfo != null);
			Contract.Invariant(this.m_finalrelmap != null);
		}

		/////////////////////////////////////////////////////////
		//general support
		private RegionGraph(RecursiveTypeInfo typeInfo, ConcreteHeap cmem)
		{
			Contract.Requires(typeInfo != null);

			this.CMem = cmem;
			this.m_nodes = new HashSet<RegionNode>();
			this.m_conctorgnmap = new Dictionary<ConcreteNode, RegionNode>();
			this.m_typeInfo = typeInfo;
			this.m_finalrelmap = new Dictionary<RegionNode, HashSet<RegionNode>>();
			this.FinalSuccMap = new Dictionary<RegionNode, List<RegionEdgeInfo>>();
			this.FinalPredMap = new Dictionary<RegionNode, List<RegionEdgeInfo>>();
		}

		/// <summary>
		/// Creates a heap graph from the concrete memory snapshot
		/// </summary>
		public static RegionGraph Create(ConcreteHeap mem, HashSet<TypeIdentifier> alltypes)
		{
			Contract.Requires(mem != null);
			Contract.Requires(alltypes != null);

			RegionGraph trp = RegionGraph.InitializeHeapWithConcrete(mem, alltypes);
			trp.Normalize();

			int totalheapbytes = trp.GetHeapSize();
			Dictionary<RegionNode, HashSet<ConcreteNode>> rgnrootmap = trp.RootNodesForRegion();

			Dictionary<RegionNode, bool> reachfromlocalmap = new Dictionary<RegionNode, bool>();
			trp.DoRootReachComps(reachfromlocalmap);
			foreach(RegionNode rn in trp.Regions)
				rn.ComputeNodeInfo(!reachfromlocalmap[rn], totalheapbytes, rgnrootmap[rn]);
			
			trp.ConstructFinalRelMap();
			return trp;
		}

		/// <summary>
		/// Creates a heap graph from the concrete memory snapshot (DOES NOT NORMALIZE)
		/// </summary>
		public static RegionGraph Create_NoNorm(ConcreteHeap mem, HashSet<TypeIdentifier> alltypes)
		{
			Contract.Requires(mem != null);
			Contract.Requires(alltypes != null);

			RegionGraph trp = RegionGraph.InitializeHeapWithConcrete(mem, alltypes);

			int totalheapbytes = trp.GetHeapSize();
			Dictionary<RegionNode, HashSet<ConcreteNode>> rgnrootmap = trp.RootNodesForRegion();

			Dictionary<RegionNode, bool> reachfromlocalmap = new Dictionary<RegionNode, bool>();
			trp.DoRootReachComps(reachfromlocalmap);
			foreach(RegionNode rn in trp.Regions)
				rn.ComputeNodeInfo(!reachfromlocalmap[rn], totalheapbytes, rgnrootmap[rn]);

			trp.ConstructFinalRelMap();
			return trp;
		}

		/// <summary>
		/// Create a new un-normalized heap from the given concrete model
		/// </summary>
		private static RegionGraph InitializeHeapWithConcrete(ConcreteHeap mem, HashSet<TypeIdentifier> alltypes)
		{
			Contract.Requires(mem != null);
			Contract.Requires(alltypes != null);

			RegionGraph rtp = new RegionGraph(new RecursiveTypeInfo(alltypes), mem);

			foreach(ConcreteNode nn in mem.AllObjects)
				rtp.AddObjectNode(nn);

			return rtp;
		}

		/// <summary>
		/// Add a node to this graph that represents all the information of the specific object <c>o</c>.
		/// </summary>
		private void AddObjectNode(ConcreteNode nn)
		{
			Contract.Requires(nn != null);

			var hr = RegionNode.InitRegionFromSingleConcreteObj(nn);
			this.m_nodes.Add(hr);
			this.m_conctorgnmap.Add(nn, hr);
		}

		/// <summary>
		/// Writes the Dgml graph to a file.
		/// </summary>
		public void WriteDgml(string fileName)
		{
			Contract.Requires(!String.IsNullOrEmpty(fileName));
			
			using(var writer = new StreamWriter(fileName))
				this.WriteDgml(writer);
		}

		/// <summary>
		/// Write the heap graph as DGML to a writer.
		/// </summary>
		public void WriteDgml(TextWriter writer)
		{
			Contract.Requires(writer != null);
			
			using(var xw = XmlWriter.Create(writer, new XmlWriterSettings { Indent = true }))
			{
				xw.WriteStartDocument();
				xw.WriteStartElement("DirectedGraph", DgmlExtensions.NamespaceUri);

				xw.WriteStartElement("Nodes");
				this.WriteNodesIntoDgml(xw);
				xw.WriteEndElement();

				xw.WriteStartElement("Links");
				this.WriteLinksIntoDgml(xw);
				xw.WriteEndElement();

				DgmlExtensions.WriteCategoriesAndProperties(xw);
				DgmlExtensions.WriteStyles(xw);
				xw.WriteEndElement();
				xw.WriteEndDocument();
			}
		}

		/// <summary>
		/// Write all the node information in this into the xmlwriter.
		/// </summary>
		public void WriteNodesIntoDgml(XmlWriter xmlw)
		{
			foreach(KeyValuePair<Tuple<String, bool>, ConcreteNode> root in this.CMem.Roots)
				this.m_conctorgnmap[root.Value].WriteDgmlForRootNode(root.Key.Item1, root.Key.Item2, xmlw);

			foreach(RegionNode hr in this.m_nodes)
				hr.WriteDgmlForRegularNode(xmlw);
		}

		/// <summary>
		/// Write all the link info from  this into the xmlwriter
		/// </summary>
		public void WriteLinksIntoDgml(XmlWriter xw)
		{
			foreach(KeyValuePair<Tuple<String, bool>, ConcreteNode> root in this.CMem.Roots)
			{
				xw.WriteStartElement("Link");
				xw.WriteAttributeString("Source", root.Key.Item1);
				xw.WriteAttributeString("Target", this.m_conctorgnmap[root.Value].RegionID.ToString());

				xw.WriteAttributeString("OnlyReachFromStatic", root.Key.Item2.ToString());

				xw.WriteAttributeString("NullEdge", root.Value.ConcreteNodeType.IsSpecialNullType.ToString());

				xw.WriteEndElement();
			}

			foreach(RegionNode hr in this.m_nodes)
			{
				foreach(RegionNode trgt in this.m_finalrelmap[hr])
				{
					HashSet<AccessPath> pathnames = new HashSet<AccessPath>();
					bool interfere;

					this.FilterEdgesIntoTargetGroups(hr, trgt, pathnames, out interfere);

					xw.WriteStartElement("Link");
					xw.WriteStartAttribute("Label");

					List<AccessPath> taccp = new List<AccessPath>(pathnames);
					taccp.Sort((AccessPath acp1, AccessPath acp2) => acp1.PathString.CompareTo(acp2.PathString));

					xw.WriteString("{");
					for(int i = 0; i < taccp.Count; ++i)
					{
						if(i != 0)
							xw.WriteString(", ");
						xw.WriteString(taccp[i].ToString());

						if(i > 2)
						{
							xw.WriteString(", ...");
							break;
						}
					}
					xw.WriteString("}");
					xw.WriteEndAttribute();

					xw.WriteAttributeString("Source", hr.RegionID.ToString());
					xw.WriteAttributeString("Target", trgt.RegionID.ToString());

					StringBuilder offsetstr = new StringBuilder("{");
					for(int i = 0; i < taccp.Count; ++i)
					{
						if(i != 0)
							offsetstr.Append(", ");
						offsetstr.Append(taccp[i].ToString());
					}
					offsetstr.Append("}");

					xw.WriteAttributeString("Offsets", offsetstr.ToString());
					xw.WriteAttributeString("OnlyReachFromStatic", hr.ExtraFacts.NotReachFromLocal.ToString());

					xw.WriteAttributeString("NullEdge", trgt.RegionTypes.Any((TypeIdentifier tt) => tt.IsSpecialNullType).ToString());

					xw.WriteAttributeString("InterferPtr", interfere.ToString());

					xw.WriteEndElement();
				}

				HashSet<AccessPath> internaloffsets = new HashSet<AccessPath>();
				foreach(ConcreteNode cn in hr.ConcreteNodeList)
				{
					foreach(ConcretePointer cp in cn.PointerTargets)
					{
						if(this.m_conctorgnmap[cp.Target] == hr)
							internaloffsets.Add(cp.LocationInSource);
					}
				}

				if(internaloffsets.Count > 0)
				{
					xw.WriteStartElement("Link");
					xw.WriteAttributeString("Id", hr.RegionID + "_self");

					xw.WriteStartAttribute("Label");

					//ewww this is not very nice
					List<AccessPath> ioffsets = new List<AccessPath>(internaloffsets);
					ioffsets.Sort((AccessPath rs1, AccessPath rs2) => (rs1.PathString.CompareTo(rs2.PathString)));

					xw.WriteString("{");
					for(int i = 0; i < ioffsets.Count; ++i)
					{
						if(i != 0)
							xw.WriteString(", ");
						xw.WriteString(ioffsets[i].ToString());

						if(i > 2)
						{
							xw.WriteString(", ...");
							break;
						}
					}
					xw.WriteString("}");
					xw.WriteEndAttribute();

					StringBuilder offsetstr = new StringBuilder("{");
					for(int i = 0; i < ioffsets.Count; ++i)
					{
						if(i != 0)
							offsetstr.Append(", ");
						offsetstr.Append(ioffsets[i].ToString());
					}
					offsetstr.Append("}");

					xw.WriteAttributeString("Offsets", offsetstr.ToString());
					xw.WriteAttributeString("OnlyReachFromStatic", hr.ExtraFacts.NotReachFromLocal.ToString());

					xw.WriteAttributeString("Source", hr.RegionID.ToString());
					xw.WriteAttributeString("Target", hr.RegionID.ToString());

					xw.WriteEndElement();
				}
			}
		}

		/// <summary>
		/// This is a helper method to deal with the fact that DGML does not support multi edges (and they could also clutter the result figure substantially).
		/// </summary>
		internal void FilterEdgesIntoTargetGroups(RegionNode n, RegionNode trgt, HashSet<AccessPath> pathnames, out bool interfere)
		{
			Contract.Requires(n != null);
			Contract.Requires(!n.RegionTypes.Any((TypeIdentifier tt) => tt.IsSpecialNullType), "Handle elsewhere");
			Contract.Requires(n != trgt, "Handle elsewhere.");
			Contract.Requires(pathnames != null && pathnames.Count == 0);

			interfere = false;

			HashSet<ConcreteNode> conctrgts = new HashSet<ConcreteNode>();
			foreach(ConcreteNode cn in n.ConcreteNodeList)
			{
				foreach(ConcretePointer cp in cn.PointerTargets)
				{
					RegionNode rgntarget = this.m_conctorgnmap[cp.Target];
					if(rgntarget != trgt)
						continue;

					if((!cp.Target.ConcreteNodeType.IsSpecialNullType) && conctrgts.Contains(cp.Target))
						interfere = true;
					conctrgts.Add(cp.Target);

					pathnames.Add(cp.LocationInSource);
				}
			}
		}

		/// <summary>
		/// Get the static mapping information
		/// </summary>
		public List<Tuple<string, bool, RegionNode>> GetRootInfo()
		{
			List<Tuple<string, bool, RegionNode>> rti = new List<Tuple<string, bool, RegionNode>>();

			foreach(KeyValuePair<Tuple<string, bool>, ConcreteNode> rr in this.CMem.Roots)
			{
				if(rr.Value.ConcreteNodeType.IsSpecialNullType)
					rti.Add(new Tuple<string, bool, RegionNode>(rr.Key.Item1, rr.Key.Item2, null));
				else
					rti.Add(new Tuple<string, bool, RegionNode>(rr.Key.Item1, rr.Key.Item2, this.m_conctorgnmap[rr.Value]));
			}

			return rti;
		}

		/// <summary>
		/// Computes the heap size in bytes
		/// </summary>
		public int GetHeapSize()
		{
			int totalheapbytes = 0;
			foreach(var hr in this.m_nodes)
				totalheapbytes += hr.ComputeTotalBytes();
			return totalheapbytes;
		}

		private void ConstructFinalRelMap()
		{
			foreach(RegionNode req in this.m_nodes)
			{
				HashSet<RegionNode> trgts = new HashSet<RegionNode>();
				foreach(ConcreteNode cn in req.ConcreteNodeList)
				{
					foreach(ConcretePointer cp in cn.PointerTargets)
					{
						RegionNode trgtrgn = this.m_conctorgnmap[cp.Target];
						if(trgtrgn != req)
							trgts.Add(trgtrgn);
					}
				}

				this.m_finalrelmap.Add(req, trgts);
			}

			this.DoDFS_WTopo(new LinkedList<RegionNode>());

			Dictionary<RegionNode, int> indegreemap = new Dictionary<RegionNode, int>();
			foreach(RegionNode nn in this.m_nodes)
			{
				indegreemap.Add(nn, 0);
				this.FinalPredMap.Add(nn, new List<RegionEdgeInfo>());
			}

			foreach(RegionNode rr in this.m_nodes)
			{
				if(rr.RegionTypes.Count == 1 && rr.RegionTypes.First().IsSpecialNullType)
					continue;

				List<RegionEdgeInfo> edgeinfo = new List<RegionEdgeInfo>();
				this.FilterPtrsForEdgeConstruction(rr, edgeinfo);

				foreach(RegionEdgeInfo oute in edgeinfo)
					indegreemap[oute.Target] = indegreemap[oute.Target] + 1;

				this.FinalSuccMap.Add(rr, edgeinfo);
			}

			foreach(ConcreteNode cn in this.CMem.Roots.Values)
			{
				if(!cn.ConcreteNodeType.IsSpecialNullType)
				{
					RegionNode trgtn = this.m_conctorgnmap[cn];
					RegionEdgeInfo.Orientation eo = (indegreemap[trgtn] > 1 ? RegionEdgeInfo.Orientation.Cross : RegionEdgeInfo.Orientation.Tree);
					FinalPredMap[trgtn].Add(new RegionEdgeInfo(null, trgtn, null, true, true, eo));
				}
			}

			foreach(RegionNode req in this.m_nodes)
			{
				if(req.RegionTypes.Count == 1 && req.RegionTypes.First().IsSpecialNullType)
					continue;

				List<RegionEdgeInfo> lerl = this.FinalSuccMap[req];
				for(int i = 0; i < lerl.Count; ++i)
				{
					RegionEdgeInfo rr = lerl[i];

					RegionEdgeInfo.Orientation eo;
					if(indegreemap[rr.Target] == 1)
						eo = RegionEdgeInfo.Orientation.Tree;
					else
					{
						if(rr.Target.TimeDiscover < req.TimeDiscover & req.TimeDiscover < rr.Target.TimeFinish)
							eo = RegionEdgeInfo.Orientation.Back;
						else
							eo = RegionEdgeInfo.Orientation.Cross;
					}

					lerl[i] = new RegionEdgeInfo(rr.Source, rr.Target, rr.Offset, rr.IsInjective, rr.IsNonNull, eo);
				}

				for(int i = 0; i < lerl.Count; ++i)
				{
					RegionEdgeInfo rr = lerl[i];
					this.FinalPredMap[rr.Target].Add(rr);
				}
			}
		}

		/// <summary>
		/// This is a helper method group the pointers into a set of edges with injectivity and nonnullitly info
		/// </summary>
		internal void FilterPtrsForEdgeConstruction(RegionNode n, List<RegionEdgeInfo> edgeinfo)
		{
			Contract.Requires(n != null);
			Contract.Requires(!n.RegionTypes.Any((TypeIdentifier tt) => tt.IsSpecialNullType), "Handle elsewhere");
			Contract.Requires(edgeinfo != null && edgeinfo.Count == 0);

			Dictionary<Tuple<AccessPath, RegionNode>, HashSet<ConcreteNode>> conctrgts = new Dictionary<Tuple<AccessPath, RegionNode>, HashSet<ConcreteNode>>();
			HashSet<Tuple<AccessPath, RegionNode>> mayalias = new HashSet<Tuple<AccessPath, RegionNode>>();
			HashSet<AccessPath> maynullinfo = new HashSet<AccessPath>();

			foreach(ConcreteNode cn in n.ConcreteNodeList)
			{
				foreach(ConcretePointer cp in cn.PointerTargets)
				{
					if(cp.Target.ConcreteNodeType.IsSpecialNullType)
						maynullinfo.Add(cp.LocationInSource);
					else
					{
						RegionNode rgntarget = this.m_conctorgnmap[cp.Target];
						Tuple<AccessPath, RegionNode> rnt = new Tuple<AccessPath, RegionNode>(cp.LocationInSource, rgntarget);

						if(!conctrgts.ContainsKey(rnt))
							conctrgts.Add(rnt, new HashSet<ConcreteNode>());

						if(conctrgts[rnt].Contains(cp.Target))
							mayalias.Add(rnt);

						conctrgts[rnt].Add(cp.Target);
					}
				}
			}

			foreach(Tuple<AccessPath, RegionNode> rnt in conctrgts.Keys)
			{
				bool isinjective = !mayalias.Contains(rnt);
				bool nonnull = !maynullinfo.Contains(rnt.Item1);

				edgeinfo.Add(new RegionEdgeInfo(n, rnt.Item2, rnt.Item1, isinjective, nonnull, RegionEdgeInfo.Orientation.UnSet));
			}
		}

		/// <summary>
		/// Return the number of nodes in the region partition.
		/// </summary>
		public int NodeCount 
		{ get { return this.m_nodes.Count; } }

		/// <summary>
		/// Return the concrete heap that underlies this region partition.
		/// </summary>
		internal ConcreteHeap BaseConcreteHeap
		{
			get
			{
				Contract.Ensures(Contract.Result<ConcreteHeap>() != null);

				return this.CMem;
			}
		}

		/// <summary>
		/// Return the nodes in this region partition.
		/// </summary>
		public HashSet<RegionNode> Regions 
		{ 
			get 
			{
				Contract.Ensures(Contract.Result<HashSet<RegionNode>>() != null);

				return this.m_nodes; 
			} 
		}

		/// <summary>
		/// Return the relation between the nodes based on the cross region pointers.
		/// </summary>
		public Dictionary<RegionNode, HashSet<RegionNode>> RegionRelationMap
		{
			get
			{
				Contract.Ensures(Contract.Result<Dictionary<RegionNode, HashSet<RegionNode>>>() != null);

				return this.m_finalrelmap;
			}
		}

		/// <summary>
		/// Return the relation between the concrete nodes and the region nodes.
		/// </summary>
		internal Dictionary<ConcreteNode, RegionNode> ContainmentMap
		{
			get
			{
				Contract.Ensures(Contract.Result<Dictionary<ConcreteNode, RegionNode>>() != null);

				return this.m_conctorgnmap;
			}
		}

		/////////////////////////////////////////////////////////
		//Traversal support

		/// <summary>
		/// Compute for all nodes and edges if they are (Not) reachable from a local root.
		/// </summary>
		private void DoRootReachComps(Dictionary<RegionNode, bool> reachfromlocalmap)
		{
			foreach(RegionNode nn in this.m_nodes)
				reachfromlocalmap.Add(nn, false);

			Queue<RegionNode> rgnq = new Queue<RegionNode>();
			foreach(KeyValuePair<Tuple<String, bool>, ConcreteNode> rr in this.CMem.Roots)
			{
				if(!rr.Key.Item2)
				{
					ConcreteNode ctrgt = rr.Value;
					RegionNode nn = this.m_conctorgnmap[ctrgt];
					reachfromlocalmap[nn] = true;
					rgnq.Enqueue(nn);
				}
			}

			while(rgnq.Count != 0)
			{
				RegionNode hr = rgnq.Dequeue();

				foreach(ConcreteNode cn in hr.ConcreteNodeList)
				{
					foreach(ConcretePointer cp in cn.PointerTargets)
					{
						ConcreteNode ctarget = cp.Target;
						RegionNode rgntarget = this.m_conctorgnmap[ctarget];
						if(!reachfromlocalmap[rgntarget])
						{
							reachfromlocalmap[rgntarget] = true;
							rgnq.Enqueue(rgntarget);
						}
					}
				}
			}
		}

		/// <summary>
		/// Prep for DFS/BFS traversal.
		/// </summary>
		private void PrepForTraversal()
		{
			RegionNode.DFSTimeCtr = 0;
			foreach(RegionNode nn in this.m_nodes)
			{
				nn.NodeColor = GraphColor.White;
				nn.TimeDiscover = -1;
				nn.TimeFinish = -1;
			}
		}

		private void DoDFSVisit(RegionNode n, LinkedList<RegionNode> sorted)
		{
			if(n.NodeColor != GraphColor.White)
				return;

			n.NodeColor = GraphColor.Gray;
			n.TimeDiscover = RegionNode.DFSTimeCtr++;
			foreach(ConcreteNode cn in n.ConcreteNodeList)
			{
				foreach(ConcretePointer cp in cn.PointerTargets)
				{
					RegionNode rgntarget = this.m_conctorgnmap[cp.Target];
					this.DoDFSVisit(rgntarget, sorted);
				}
			}

			sorted.AddFirst(n);
			n.NodeColor = GraphColor.Black;
			n.TimeFinish = RegionNode.DFSTimeCtr++;
		}

		private void DoDFS_WTopo(LinkedList<RegionNode> sorted)
		{
			this.PrepForTraversal();
			foreach(ConcreteNode cn in this.CMem.Roots.Values)
			{
				RegionNode req = this.m_conctorgnmap[cn];
				this.DoDFSVisit(req, sorted);
			}
		}

		/////////////////////////////////////////////////////////
		//Normalize Routines

		/// <summary>
		/// Given a set of partitions merge and them, and return the newly created partition.
		/// </summary>
		private RegionNode MergePartitions(HashSet<RegionNode> tomerge)
		{
			RegionNode rr = RegionNode.JoinRegionEqClasses(tomerge);

			foreach(ConcreteNode cn in rr.ConcreteNodeList)
				this.m_conctorgnmap[cn] = rr;

			foreach(RegionNode req in tomerge)
				this.m_nodes.Remove(req);
			this.m_nodes.Add(rr);

			return rr;
		}

		/// <summary>
		/// Remove ambig targets from a node. That is look at all the out edges and find those that have BOTH the same edges labels and refer to "equivalent" nodes.
		/// Where equivalence is defined by the method <c>RegionEqClass.OkToMerge</c>.
		/// </summary>
		/// <param name="nn">The node we are removing ambig targets from.</param>
		/// <param name="toProc">The pending list to process, add newly created nodes to the front.</param>
		private void MergeAmbigTargets(RegionNode nn, LinkedList<RegionNode> toProc)
		{
			Contract.Requires(nn != null);
			Contract.Requires(this.m_nodes.Contains(nn), "Already removed??");
			Contract.Requires(toProc != null);

			LinkedList<PredMergeEnty> mergelist = new LinkedList<PredMergeEnty>();

			for(int i = 0; i < nn.ConcreteNodeList.Count; ++i)
			{
				ConcreteNode cn = nn.ConcreteNodeList[i];

				for(int j = 0; j < cn.PointerTargets.Length; ++j)
				{
					AccessPath pth = cn.PointerTargets[j].LocationInSource;
					RegionNode trgt = this.m_conctorgnmap[cn.PointerTargets[j].Target];

					if(trgt == nn)
						continue;

					PredMergeEnty npe = new PredMergeEnty(trgt, pth);
					mergelist.AddFirst(npe);
				}
			}

			LinkedListNode<PredMergeEnty> cursori = mergelist.First;
			while(cursori != null)
			{
				PredMergeEnty mergeinto = cursori.Value;
				LinkedListNode<PredMergeEnty> cursorj = mergelist.First;

				while(cursorj != null)
				{
					LinkedListNode<PredMergeEnty> current = cursorj;
					cursorj = cursorj.Next;
					PredMergeEnty cmerge = current.Value;
					
					if((mergeinto != cmerge) && (cmerge.IsEntryEquivWith(mergeinto) || cmerge.RegionSet.Overlaps(mergeinto.RegionSet)))
					{
						mergeinto.MergeIntoThis(cmerge);
						mergelist.Remove(current);
					}
				}

				cursori = cursori.Next;
			}

			/*
			LinkedList<PredMergeEnty> mergelist = new LinkedList<PredMergeEnty>();

			for(int i = 0; i < nn.ConcreteNodeList.Count; ++i)
			{
				ConcreteNode cn = nn.ConcreteNodeList[i];
				for(int j = 0; j < cn.PointerTargets.Length; ++j)
				{
					AccessPath pth = cn.PointerTargets[j].LocationInSource;
					RegionNode trgt = this.m_conctorgnmap[cn.PointerTargets[j].Target];

					if(trgt == nn)
						continue;

					PredMergeEnty npe = new PredMergeEnty(trgt, pth);
					mergelist.AddFirst(npe);

					PredMergeEnty mergeinto = npe;
					LinkedListNode<PredMergeEnty> cursor = mergelist.First;
					LinkedListNode<PredMergeEnty> current;

					while(cursor != null)
					{
						current = cursor;
						cursor = cursor.Next;

						PredMergeEnty cmerge = current.Value;
						if((mergeinto != cmerge) && (cmerge.IsEntryEquivWith(mergeinto) || cmerge.RegionSet.Overlaps(mergeinto.RegionSet)))
						{
							mergeinto.MergeIntoThis(cmerge);
							mergelist.Remove(current);
						}
					}
				}
			}
			*/
			
			foreach(PredMergeEnty pme in mergelist)
			{
				if(pme.RegionSet.Count > 1)
				{
					RegionNode rr = this.MergePartitions(pme.RegionSet);
					toProc.AddFirst(rr);
				}
			}
		}

		private class PredMergeEnty
		{
			internal HashSet<TypeIdentifier> TypeSet;
			internal HashSet<RegionNode> RegionSet;
			internal HashSet<AccessPath> PathFromParentSet;

			internal PredMergeEnty(RegionNode rn, AccessPath inpath)
			{
				this.TypeSet = new HashSet<TypeIdentifier>(rn.RegionTypes);
				
				this.RegionSet = new HashSet<RegionNode>();
				this.RegionSet.Add(rn);

				this.PathFromParentSet = new HashSet<AccessPath>();
				this.PathFromParentSet.Add(inpath);
			}

			internal bool IsEntryEquivWith(PredMergeEnty pme)
			{
				return this.TypeSet.Overlaps(pme.TypeSet) && this.PathFromParentSet.Overlaps(pme.PathFromParentSet);
			}

			internal void MergeIntoThis(PredMergeEnty other)
			{
				Contract.Requires(this != other);

				this.TypeSet.UnionWith(other.TypeSet);
				this.RegionSet.UnionWith(other.RegionSet);
				this.PathFromParentSet.UnionWith(other.PathFromParentSet);
			}
		}

		/*
		/// <summary>
		/// Remove ambig targets from a node. That is look at all the out edges and find those that have BOTH the same edges labels and refer to "equivalent" nodes.
		/// Where equivalence is defined by the method <c>RegionEqClass.OkToMerge</c>.
		/// </summary>
		/// <param name="nn">The node we are removing ambig targets from.</param>
		/// <param name="toProc">The pending list to process, add newly created nodes to the front.</param>
		private void MergeAmbigTargets(RegionNode nn, LinkedList<RegionNode> toProc)
		{
			Contract.Requires(nn != null);
			Contract.Requires(this.m_nodes.Contains(nn), "Already removed??");
			Contract.Requires(toProc != null);

			List<ConcretePointer> eidv = new List<ConcretePointer>();
			for(int i = 0; i < nn.ConcreteNodeList.Count; ++i)
				eidv.AddRange(nn.ConcreteNodeList[i].PointerTargets);
			eidv.Sort();

			HashSet<RegionNode> tomerge = new HashSet<RegionNode>();
			int ei = 0;
			int eu;
			while(ei < eidv.Count)
			{
				eu = ei + 1;
				while(eu < eidv.Count && eidv[eu].LocationInSource == eidv[ei].LocationInSource)
					++eu;

				//we need at least 2 edges for this to be interesting
				for(int i = ei; i < eu; ++i)
				{
					RegionNode reqi = this.m_conctorgnmap[eidv[i].Target];
					tomerge.Clear();
					tomerge.Add(reqi);

					for(int j = ei + 1; j < eu; ++j)
					{
						RegionNode reqj = this.m_conctorgnmap[eidv[j].Target];

						if(reqi != reqj && RegionNode.OkToMerge(reqi, reqj))
							tomerge.Add(reqj);
					}

					//we ignore self edges
					tomerge.Remove(nn);

					if(tomerge.Count > 1)
					{
						RegionNode rr = this.MergePartitions(tomerge);
						toProc.AddFirst(rr);
					}
				}

				ei = eu;
			}
		}
		*/

		/// <summary>
		/// Process a single node for recursive structure elmination. Start from n, find the extent of any recursive structures and merge 
		/// the entire structure into a summary node. Updates the graph structure as needed, note we don't need to worry about updating the 
		/// outside worklist as this method already extracted the maximal recursive extent of the structure (and if we create a new node we 
		/// return it, otherwise we return null).
		/// </summary>
		/// <param name="n">The node we are starting the recursive merge from.</param>
		private RegionNode DoRecTypesNormSingle(RegionNode n)
		{
			Contract.Requires(n != null);
			Contract.Requires(this.m_nodes.Contains(n), "Already removed??");

			HashSet<TypeIdentifier> recwithset = new HashSet<TypeIdentifier>();

			HashSet<RegionNode> toMerge = new HashSet<RegionNode>();
			Queue<RegionNode> pending = new Queue<RegionNode>();
			pending.Enqueue(n);
			toMerge.Add(n);
			while(pending.Count > 0)
			{
				RegionNode pr = pending.Dequeue();
				
				recwithset.Clear();
				this.m_typeInfo.ComputeRecWithSetForSetOfTypes(pr.RegionTypes, recwithset);

				foreach(ConcreteNode cn in pr.ConcreteNodeList)
				{
					foreach(ConcretePointer cp in cn.PointerTargets)
					{
						RegionNode rr = this.m_conctorgnmap[cp.Target];
						bool recTypes = recwithset.Overlaps(rr.RegionTypes);
						if(recTypes && (!toMerge.Contains(rr)))
						{
							toMerge.Add(rr);
							pending.Enqueue(rr);
						}
					}
				}
			}

			if(toMerge.Count > 1)
			{
				RegionNode rr = this.MergePartitions(toMerge);
				rr.NodeColor = GraphColor.Black;
				return rr;
			}
			else
				return null;
		}

		/// <summary>
		/// This is the externally exposed normalize routine, call it on the initial "isomorphic to the concrete heap graph" version of the abstract graph.
		/// </summary>
		private void Normalize()
		{
			LinkedList<RegionNode> toProc = new LinkedList<RegionNode>();
			this.DoDFS_WTopo(toProc);
			while(toProc.Count != 0)
			{
				RegionNode ntp = toProc.First();
				toProc.RemoveFirst();
				if(this.m_nodes.Contains(ntp))
				{
					RegionNode mergedrecinto = this.DoRecTypesNormSingle(ntp);
					if(mergedrecinto != null)
						ntp = mergedrecinto;

					this.MergeAmbigTargets(ntp, toProc);
				}
			}
		}

		///////////////////////////////
		//Helper code to do the computation of factored data structures.

		/// <summary>
		/// Return true if the given region node has no internal connectivity.
		/// </summary>
		internal bool IsAtom(RegionNode rn)
		{
			foreach(ConcreteNode cn in rn.ConcreteNodeList)
			{
				foreach(ConcretePointer cp in cn.PointerTargets)
				{
					RegionNode cprgntrgt = this.m_conctorgnmap[cp.Target];
					if(cprgntrgt == rn)
						return false;
				}
			}

			return true;
		}

		internal Dictionary<RegionNode, HashSet<RegionNode>> BuildPredNodeMap()
		{
			Dictionary<RegionNode, HashSet<RegionNode>> predmap = new Dictionary<RegionNode,HashSet<RegionNode>>();

			foreach(RegionNode rn in this.m_nodes)
				predmap.Add(rn, new HashSet<RegionNode>());

			foreach(RegionNode rn in this.m_nodes)
			{
				foreach(RegionNode trgt in this.m_finalrelmap[rn])
					predmap[trgt].Add(rn);
			}

			return predmap;
		}

		/// <summary>
		/// Return true if the region node has exactly one incomming edge and this edge consists of all injective pointers
		/// </summary>
		internal bool HasUniqueInEdgeAndIsInjective(RegionNode rn, Dictionary<RegionNode, HashSet<RegionNode>> prednodemap)
		{
			List<RegionNode> rnl = new List<RegionNode>(prednodemap[rn]);
			if(rnl.Count != 1)
				return false;

			RegionNode parnode = rnl[0];
			HashSet<ConcreteNode> seentrgts = new HashSet<ConcreteNode>();

			foreach(ConcreteNode cn in parnode.ConcreteNodeList)
			{
				foreach(ConcretePointer cp in cn.PointerTargets)
				{
					RegionNode trgn = this.m_conctorgnmap[cp.Target];
					if(trgn == rn && seentrgts.Contains(cp.Target))
						return false;

					seentrgts.Add(cp.Target);
				}
			}

			return true;
		}

		/// <summary>
		/// Return true if this region consists of objects of a single small type (and if it is a container that the size is constant and small).
		/// </summary>
		internal static bool RegionIsSingleSmallType(RegionNode rn)
		{
			if(rn.RegionTypes.Count != 1)
				return false;

			TypeIdentifier tt = new List<TypeIdentifier>(rn.RegionTypes)[0];
			if(tt.IsArrayType)
			{
				int csize = rn.ConcreteNodeList[0].ContainerSizeInfo;
				if(csize > 3)
					return false;

				return rn.ConcreteNodeList.All((ConcreteNode cn) => (cn.ContainerSizeInfo == csize));
			}
			else if(tt.IsObjectType)
			{
				if(tt.NameValue.Equals("System.String"))
					return false;

				return (tt.AllOffsetIdentifiers.Count <= 3);
			}
			else
			{
				return false;
			}
		}

		/// <summary>
		/// For each region in the graph compute the objects in the region that are roots within the region (e.g. have a pointer to them from 
		/// a object in another region).
		/// </summary>
		internal Dictionary<RegionNode, HashSet<ConcreteNode>> RootNodesForRegion()
		{
			Dictionary<RegionNode, HashSet<ConcreteNode>> rrs = new Dictionary<RegionNode, HashSet<ConcreteNode>>();

			foreach(RegionNode rn in this.m_nodes)
				rrs.Add(rn, new HashSet<ConcreteNode>());


			HashSet<ConcreteNode> visited = new HashSet<ConcreteNode>();
			Queue<ConcreteNode> pending = new Queue<ConcreteNode>();
			foreach(ConcreteNode cn in this.CMem.Roots.Values)
			{
				if(visited.Contains(cn))
					continue;

				pending.Enqueue(cn);
				rrs[this.m_conctorgnmap[cn]].Add(cn);
				visited.Add(cn);
			}

			while(pending.Count != 0)
			{
				ConcreteNode cn = pending.Dequeue();

				foreach(ConcretePointer cp in cn.PointerTargets)
				{
					if(visited.Contains(cp.Target))
						continue;

					if(this.m_conctorgnmap[cn] != this.m_conctorgnmap[cp.Target])
						rrs[this.m_conctorgnmap[cp.Target]].Add(cp.Target);

					pending.Enqueue(cp.Target);
					visited.Add(cp.Target);
				}
			}

			return rrs;
		}
	}
}


